//TODO: LeetCode105. 从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //preI确定根 inBegin和inEnd确定根的左右子树一共所占的区间范围
        int preI = 0, inBegin = 0, inEnd = inorder.size() - 1;
        return _buildTree(preorder, inorder, preI, inBegin, inEnd);
    }

    //因为preI是要根据递归的次数（或构造完成的程度）来变化的 所以要加上引用 保证其能被所有层次的递归修改
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& preI, int inBegin, int inEnd)
    {
        if (inBegin > inEnd) return nullptr;

        TreeNode* root = new TreeNode(preorder[preI]);
        int inRootI = inBegin;
        while(inRootI <= inEnd) //确定当前的根在中序遍历数组中的位置
        {
            if (inorder[inRootI] == preorder[preI]) break;
            ++inRootI;
        }

        if (inBegin < inRootI) //保证下标的合法性
        {
            root->left = _buildTree(preorder, inorder, ++preI, inBegin, inRootI - 1);
        }

        if (inRootI < inEnd)
        {
            root->right = _buildTree(preorder, inorder, ++preI, inRootI + 1, inEnd);
        }

        return root;
    }
};